package letcode.oneQuestionPerDay._202004._21;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: 统计【优美子数组】
 * @Date: 2020/4/21
 * @Author: 许群星
 */
public class StaticsPefectArrays_b {
    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 1, 1};
        int k = 3;
        int[] arr1 = {2, 4, 6};
        int k1 = 1;
        int[] arr2 = {2, 2, 2, 1, 2, 2, 1, 2, 2, 2};
        int k2 = 2;
        int[] arr3 = {91473, 45388, 24720, 35841, 29648, 77363, 86290, 58032, 53752, 87188, 34428, 85343, 19801, 73201};
        int k3 = 4;

        System.out.println(numberOfSubarrays(arr3, k3));

    }

    //提供方法    官方题解：数学
    public static int numberOfSubarrays(int[] nums, int k) {
        //(odd[i]−odd[i−1])∗(odd[i+k]−odd[i+k−1])
        int n=nums.length;
        int[] odd=new int[n+2];
        int ans=0,cnt=0;

        for (int i = 0; i < n; i++) {
            if ((nums[i]&1)==1)
                odd[++cnt]=i;
        }
        odd[0]=-1;
        odd[++cnt]=n;
        for (int i = 1; i+k<=cnt; i++) {
            ans+=(odd[i]-odd[i-1])*(odd[i+k]-odd[i+k-1]);
        }
        return ans;
    }
}
/*
给你一个整数数组 nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。
示例 1：

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：

输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3：

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16
 

提示：

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */